import java.util.*;

public class Solution {
    /**
     * 课程表
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> hash = new HashMap<>();
        int[] indegree = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++) {
            int prev = prerequisites[i][1];
            int next = prerequisites[i][0];
            List<Integer> list = hash.getOrDefault(prev, new ArrayList<>());
            list.add(next);
            hash.put(prev, list);
            indegree[next]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }
        int n = 0;
        while(!queue.isEmpty()) {
            int key = queue.poll();
            // 删除边
            List<Integer> list = hash.get(key);
            if (list == null) {
                continue;
            }
            for(Integer i: list) {
                indegree[i]--;
                if (indegree[i] == 0) {
                    queue.add(i);
                }
            }
            n++;
        }
        return numCourses == n;
    }

    /**
     * 课程表II
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ret = new int[numCourses];
        int[] in = new int[numCourses]; // 入度
        Map<Integer, List<Integer>> hash = new HashMap<>(); // 邻接表
        for(int[] x: prerequisites) {
            in[x[0]]++;
            List<Integer> tmp = hash.getOrDefault(x[1], new ArrayList<>());
            tmp.add(x[0]);
            hash.put(x[1], tmp);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < in.length; i++) {
            if (in[i] == 0) {
                queue.add(i);
            }
        }
        int j = 0;
        while(!queue.isEmpty()) {
            int k = queue.poll();
            ret[j++] = k;
            List<Integer> tmp = hash.get(k);
            if (tmp != null) {
                for(int x: tmp) {
                    in[x]--;
                    if (in[x] == 0) {
                        queue.add(x);
                    }
                }
            }
        }
        for(int i = 0; i < in.length; i++) {
            if (in[i] != 0) {
                return new int[]{};
            }
        }
        return ret;
    }

    /**
     * 火星词典
     * @param words
     * @return
     */
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> edges = new HashMap<>(); // 邻接表
        Map<Character, Integer> in = new HashMap<>(); // 入度
        // 初始化
        for(String s: words) {
            for(int i = 0; i < s.length(); i++) {
                in.put(s.charAt(i), 0);
            }
        }
        // 统计信息
        int len = words.length;
        for(int i = 0; i < len; i++) {
            for(int j = i + 1; j < len; j++) {
                int cur = 0;
                while(cur < words[i].length() && cur < words[j].length()) {
                    char ch1 = words[i].charAt(cur);
                    char ch2 = words[j].charAt(cur);
                    if (ch1 == ch2) {
                        cur++;
                    } else {
                        Set<Character> tmp = edges.getOrDefault(ch1, new HashSet<>());
                        if (!tmp.contains(ch2)) {
                            in.put(ch2, in.get(ch2) + 1);
                            tmp.add(ch2);
                            edges.put(ch1, tmp);
                        }
                        break;
                    }
                }
                if (cur == words[j].length() && cur < words[i].length()) {
                    return "";
                }
            }
        }
        StringBuilder ret = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        for(char ch: in.keySet()) {
            if (in.get(ch) == 0) {
                queue.add(ch);
            }
        }
        while(!queue.isEmpty()) {
            char key = queue.poll();
            ret.append(key);
            Set<Character> tmp = edges.get(key);
            if (tmp != null) {
                for(char ch: tmp) {
                    int count = in.get(ch) - 1;
                    in.put(ch, count);
                    if (count == 0) {
                        queue.add(ch);
                    }
                }
            }
        }
        for(char ch: in.keySet()) {
            if (in.get(ch) != 0) {
                return "";
            }
        }
        return ret.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
       // solution.canFinish(2, new int[][] {{1, 0}});
        String[] words = {"wrt","wrtkj"};
        solution.alienOrder(words);
    }
}
